package com.lsa.letcode.the108.sortedArrToBst;

import com.lsa.letcode.common.TreeNode;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
    	return sortedArrayToBST(nums, 0, nums.length - 1);
    }
    
    public TreeNode sortedArrayToBST(int[] nums, int from, int to) {
    	if (from > to) {
    		return null;
    	}
        int mid = (from + to) >> 1;
        
    	int idx = mid;
    	
    	// UNCOMMENT to create BST (unbalanced) with prop each(left) < root <= each(right)
    	// int idx = indexOfLessOrEq(nums, from, mid);
    	
        TreeNode n = new TreeNode(nums[idx]);
        n.left = sortedArrayToBST(nums, from, idx - 1);
        n.right = sortedArrayToBST(nums, idx + 1, to);
        return n;
    }
    
    @SuppressWarnings("unused")
	private int indexOfLessOrEq(int[] nums, int from, int to) {
    	int val = nums[to];
    	while(from <= to) {
    		int mid = (from + to) >> 1;
    		if (nums[mid] < val) {
    			from = mid + 1;
    		}
    		else { // nums[mid] === val
    			if (mid > from) {
    				if (nums[mid - 1] < nums[mid]) {
    					return mid;
    				}
    				else { //nums[mid - 1] === nums[mid]
    					to = mid - 1;
    				}
    			}
    			else { // nums[mid] === val AND mid === from
    				return mid;
    			}
    		}
    	}
    	return -1;
    }
}